package com.zhugang.week12;

import java.util.HashMap;
import java.util.Map;

/**
 * @program algorithms
 * @description: minWindow3
 * @author: chanzhugang
 * @create: 2022/09/09 09:24
 */
public class MinWindow3 {

    /**
     * 76 最小覆盖子串
     * 滑动窗口解决：子串问题
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindwo3(String s, String t) {
        Map<Character, Integer> tmap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            // 统计模式串单词频次
            update(tmap, t.charAt(i), 1);
        }

        int minSize = Integer.MAX_VALUE;
        int minL = -1;
        int minR = -1;

        // 滑动窗口
        Map<Character, Integer> wmap = new HashMap<>();
        int n = s.length();
        int l = 0;
        int r = -1;
        while (l < n && r < n) {
            if (!match(wmap, tmap)) {
                // 覆盖
                r++;
                if (r > n - 1) {
                    break;
                }
                update(wmap, s.charAt(r), 1);
            } else {
                // 没有覆盖
                if (minSize > r - l + 1) {
                    minSize = r - l + 1;
                    minL = l;
                    minR = r;
                }
                update(wmap, s.charAt(l), -1);
                l++;
            }
        }

        if (minL == -1) {
            return "";
        }
        return s.substring(minL, minR + 1);
    }

    private boolean match(Map<Character, Integer> wmap, Map<Character, Integer> tmap) {
        for (Map.Entry<Character, Integer> entry : tmap.entrySet()) {
            Character key = entry.getKey();
            if (!wmap.containsKey(key)) return false;
            if (wmap.get(key) < entry.getValue()) return false;
        }
        return true;
    }

    private void update(Map<Character, Integer> map, char c, int count) {
        if (map.containsKey(c)) {
            count += map.get(c);
        }
        map.put(c, count);
    }
}